#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int q[N], n;
//
//int mid_num(int* a, int l, int r)
//{
//	int mid = (l + r) >> 1;
//	if (a[l] > a[r])
//	{
//		if (a[r] > a[mid]) return r;
//		else if (a[l] < a[mid]) return l;
//		else return mid;
//	}
//	else
//	{
//		if (a[l] > a[mid]) return l;
//		else if (a[r] < a[mid]) return r;
//		else return mid;
//	}
//}
//
//void quick_sort(int* a, int l, int r)
//{
//	if (l >= r) return;
//
//	int mid = mid_num(a, l, r);
//	swap(a[mid], a[l]);
//	int x = a[l], i = l - 1, j = r + 1;
//
//	while (i < j)
//	{
//		do i++; while (a[i] < x);
//		do j--; while (a[j] > x);
//		if (i < j) swap(a[i], a[j]);
//	}
//
//	quick_sort(a, l, j);
//	quick_sort(a, j + 1, r);
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	quick_sort(q, 0, n - 1);
//
//	for (int i = 0; i < n; i++) cout << q[i] << ' ';
//	cout << endl;
//
//	return 0;
//}


//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int q[N], k, n;
//
//int mid_num(int* a, int l, int r)
//{
//	int mid = (l + r) >> 1;
//	if (a[l] > a[r])
//	{
//		if (a[r] > a[mid]) return r;
//		else if (a[l] < a[mid]) return l;
//		else return mid;
//	}
//	else
//	{
//		if (a[l] > a[mid]) return l;
//		else if (a[r] < a[mid]) return r;
//		else return mid;
//	}
//}
//
//int quick_sort(int* a, int l, int r, int k)
//{
//	if (l >= r) return a[l];
//
//	int mid = mid_num(a, l, r);
//	swap(a[mid], a[l]);
//	int x = a[l], i = l - 1, j = r + 1;
//
//	while (i < j)
//	{
//		do i++; while (a[i] < x);
//		do j--; while (a[j] > x);
//		if (i < j) swap(a[i], a[j]);
//	}
//
//	int sn = j - l + 1;
//	if (sn >= k) return quick_sort(a, l, j, k);
//	else return quick_sort(a, j + 1, r, k - sn);
//}
//
//int main()
//{
//	cin >> n >> k;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	cout << quick_sort(q, 0, n - 1, k) << endl;
//
//	return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int tmp[N], q[N], n;
//
//void merge_sort(int* a, int l, int r)
//{
//    if (l >= r) return;
//
//    int mid = (l + r) >> 1;
//    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
//
//    int k = 0, i = l, j = mid + 1;
//    while (i <= mid && j <= r)
//        if (a[i] < a[j]) tmp[k++] = a[i++];
//        else tmp[k++] = a[j++];
//    while (i <= mid) tmp[k++] = a[i++];
//    while (j <= r) tmp[k++] = a[j++];
//
//    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> q[i];
//
//    merge_sort(q, 0, n - 1);
//
//    for (int i = 0; i < n; i++) cout << q[i] << ' ';
//    cout << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//typedef long long LL;
//
//const int N = 100010;
//int n, q[N], tmp[N];
//
//LL merge_sort(int l, int r)
//{
//    if (l >= r) return 0;
//
//    int mid = (l + r) >> 1;
//    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
//
//    int k = 0, i = l, j = mid + 1;
//    while (i <= mid && j <= r)
//    {
//        if (q[i] <= q[j]) tmp[k++] = q[i++];
//        else
//        {
//            res += mid - i + 1;
//            tmp[k++] = q[j++];
//        }
//    }
//    while (i <= mid) tmp[k++] = q[i++];
//    while (j <= r) tmp[k++] = q[j++];
//
//    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//
//    return res;
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> q[i];
//
//    cout << merge_sort(0, n - 1) << endl;
//
//    return 0;
//}


